package com.ztom.daily.n2022.m4;

/**
 * 旋转字符串
 * <p>
 * https://leetcode-cn.com/problems/rotate-string/
 *
 * @author ZhangTao
 */
public class Day07RotateString {

    public boolean rotateString(String s, String goal) {
        if (s == null || s.length() == 0) {
            return false;
        }

        return s.length() == goal.length() && kmp(s + s, goal);
    }

    private boolean kmp(String s, String t) {
        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();
        int x = 0;
        int y = 0;
        int[] next = getNextArray(str2);
        while (x < str1.length && y < str2.length) {
            if (str1[x] == str2[y]) {
                x++;
                y++;
            } else if (next[y] == -1) {
                x++;
            } else {
                y = next[y];
            }
        }
        return y == str2.length;
    }

    private int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        next[0] = -1;
        next[1] = 0;

        int index = 2;
        int cn = 0;

        while (index < str2.length) {
            if (str2[index - 1] == str2[cn]) {
               next[index++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[index++] = 0;
            }
        }
        return next;
    }
}
